/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package org.amit.collections;

import java.util.*;

public class BKTree<T> {

public static class BKnode<T> {
  public T Payload;

        public BKnode<T>[] Children = new BKnode[0];



        public BKnode(T payload)
        {
            Payload = payload;
            this.Children = new BKnode[0];
        }

        public boolean AddChild(int distance, T childPayload)
        {
            if(Children.length - 1 < distance)
                Children = Arrays.copyOf(Children, distance+1);
            System.out.println("new length is " + Children.length + " and distance is " + distance);
            if (Children[distance] == null)
            {
                Children[distance] = new BKnode<T>(childPayload);
                return true;
            }
            return false;
        }
}



    public interface Distancer<T> {

        public int getDistance(T payload, T element);
    }
    public Distancer distanceFunction;
    //    private readonly DistanceDelegate distance = null;
    private BKnode<T> root = null;

    public BKTree(Distancer distanceFunction) {
        this.distanceFunction = distanceFunction;
    }

    public void Add(T element) {
        if (root == null) {
            root = new BKnode<T>(element);
        }

        BKnode<T> actual = root;
        boolean done = false;
        while (!done) {
            int dist = distanceFunction.getDistance(actual.Payload, element);
            if (actual.AddChild(dist, element)) {
                done = true;
            } else {
                actual = actual.Children[dist];
            }
        }
    }

    public List<T> Query(int n, T element) {
        List<T> elms = new ArrayList<T>();
        query_r(root, n, element, elms);
        return elms;
    }

    public boolean HasQueryResults(int n, T element) {
        return queryResults_r(root, n, element);
    }

    private void query_r(BKnode<T> actual, int n, T element, List<T> takenElements) {
        if (actual == null) {
            return;
        }

        int dist = distanceFunction.getDistance(actual.Payload, element);
        if (dist <= n) {
            takenElements.add(actual.Payload);
        }

        int mini = dist - n < 0 ? 0 : dist - n;
        int maxi = dist + n > actual.Children.length - 1 ? actual.Children.length - 1 : dist + n;

        for (int i = mini; i <= maxi; i++) {
            query_r(actual.Children[i], n, element, takenElements);
        }

    }

    private boolean queryResults_r(BKnode<T> actual, int n, T element) {
        if (actual == null) {
            return false;
        }

        int dist = distanceFunction.getDistance(actual.Payload, element);
        if (dist <= n) {
            return true;
        }

        int mini = dist - n < 0 ? 0 : dist - n;
        int maxi = dist + n > actual.Children.length - 1 ? actual.Children.length - 1 : dist + n;

        for (int i = mini; i <= maxi; i++) {
            if (queryResults_r(actual.Children[i], n, element)) {
                return true;
            }
        }
        return false;
    }
}
